package leetcode.动态规划.middle;

/**
 * @author wangmaolin1
 * @date 2023/11/14 22:04
 */
public class _53 {
    /**
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 子数组 是数组中的一个连续部分。
     * 定义dp[i]:到0-i的最大和
     * dp[0] = nums[0]
     * dp[i] = dp[i-1]+nums[i] > nums[i] ? dp[i-1]+nums[i]:nums[i]
     * maxSum = dp[0]
     *maxSum =  max(dp[i],maxSum)
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i-1]+nums[i] > nums[i]){
                dp[i] = dp[i-1]+nums[i];
            }else {
                dp[i] = nums[i];
            }
            maxSum = Math.max(maxSum,dp[i]);
        }
        return maxSum;
    }
    public int maxSubArray2(int[] nums) {
        int dp_0 = nums[0];
        int dp_i = 1;
        int maxSum = dp_0;
        for (int i = 1; i < nums.length; i++) {
            if(dp_0 + nums[i]>nums[i]){
                dp_i = dp_0 + nums[i];
            }else {
                dp_i =  nums[i];
            }
            dp_0  = dp_i;
            maxSum = Math.max(maxSum,dp_i);
        }
        return maxSum;
    }
}
